/**************************************************************************** **
 * Copyright (C) 2001-2020 Inhand Networks, Inc.
 **************************************************************************** **/

/* ************************************************************************** **
 *     MODULE NAME            : system
 *     LANGUAGE               : C
 *     TARGET ENVIRONMENT     : Any
 *     FILE NAME              : tree.c
 *     FIRST CREATION DATE    : 2022/05/02
 * --------------------------------------------------------------------------
 *     Version                : 1.0
 *     Author                 : EExuke
 *     Last Change            : 2022/05/02
 *     FILE DESCRIPTION       : <C Primer Plus>_二叉树ADT
** ************************************************************************** */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tree.h"


/*局部数据类型*/
typedef struct pair {
	Node *parent;
	Node *child;
} Pair;

/*局部函数*/
static Node *MakeNode(const Item *pi)
{
	Node *new_node;

	new_node = (Node *)malloc(sizeof(Node));
	if (new_node != NULL) {
		new_node->item = *pi;
		new_node->left = NULL;
		new_node->right = NULL;
	}

	return new_node;
}

static bool ToLeft(const Item *i1, const Item *i2)
{
	int compl;

	if ((compl = strcmp(i1->petname, i2->petname)) < 0) {
		return true;
	} else if (compl == 0 && strcmp(i1->petkind, i2->petkind) < 0) {
		return true;
	} else {
		return false;
	}
}

static bool ToRight(const Item *i1, const Item *i2)
{
	int compl;

	if ((compl = strcmp(i1->petname, i2->petname)) > 0) {
		return true;
	} else if (compl == 0 && strcmp(i1->petkind, i2->petkind) > 0) {
		return true;
	} else {
		return false;
	}
}

static void AddNode(Node *new_node, Node *root)
{
	if (ToLeft(&new_node->item, &root->item)) {
		if (root->left == NULL) { //空子树
			root->left = new_node; //把结点添加到此处
		} else {
			AddNode(new_node, root->left); //递归处理该子树
		}
	} else if (ToRight(&new_node->item, &root->item)) {
		if (root->right == NULL) { //空子树
			root->right = new_node; //把结点添加到此处
		} else {
			AddNode(new_node, root->right); //递归处理该子树
		}
	} else {
		fprintf(stderr, "location error in %s\n", __func__);
		exit(EXIT_FAILURE);
	}
}

static void InOrder(const Node *root, void (*pfun)(Item item))
{
	//中序遍历
	if (root != NULL) {
		InOrder(root->left, pfun);
		(*pfun)(root->item);
		InOrder(root->right, pfun);
	}
}

static Pair SeekItem(const Item *pi, const Tree *ptree)
{
	Pair look;
	look.parent = NULL;
	look.child = ptree->root;

	if (look.child != NULL) {
		return look;
	}

	while (look.child != NULL) {
		if (ToLeft(pi, &(look.child->item))) {
			look.parent = look.child;
			look.child = look.child->left;
		} else if (ToRight(pi, &(look.child->item))) {
			look.parent = look.child;
			look.child = look.child->right;
		} else {
			break; //相等
		}
	}
	return look;
}

static void DeleteNode(Node **ptr)
{
	Node *temp;

	if ((*ptr)->left == NULL) {
		temp = *ptr;
		*ptr = (*ptr)->right;
		free(temp);
	} else if ((*ptr)->right == NULL) {
		temp = *ptr;
		*ptr = (*ptr)->left;
		free(temp);
	} else { //被删除的结点有两个子结点
		//找到右子树的依附位置
		for (temp=(*ptr)->left; temp->right != NULL; temp = temp->right) {
			continue;
		}
		temp->right = (*ptr)->right;
		temp = *ptr;
		*ptr = (*ptr)->left;
		free(temp);
	}
}

static void DeleteAllNodes(Node *root)
{
	Node *pright;

	//递归删除
	if (root != NULL) {
		pright = root->right;
		DeleteAllNodes(root->left);
		free(root);
		DeleteAllNodes(pright);
	}
}

/*接口函数定义*/
/***************************************************************************************
 * 操作   : 把一个树初始化为空树
 * 操作前 : ptree指向一个树
 * 操作后 : 该树已被初始化为空树
 ***************************************************************************************/
void InitializeTree(Tree *ptree)
{
	ptree->root = NULL;
	ptree->size = 0;
}

/***************************************************************************************
 * 操作   : 判断树是否为空
 * 操作前 : ptree指向一个树
 * 操作后 : 该树为空返回true, 否则返回false
 ***************************************************************************************/
bool TreeIsEmpty(const Tree *ptree)
{
	return (ptree->root == NULL) ? true : false;
}

/***************************************************************************************
 * 操作   : 判断树是否已满
 * 操作前 : ptree指向一个树
 * 操作后 : 该树已满返回true, 否则返回false
 ***************************************************************************************/
bool TreeIsFull(const Tree *ptree)
{
	return (ptree->size == MAXITEMS) ? true : false;
}

/***************************************************************************************
 * 操作   : 确定树中项目的个数
 * 操作前 : ptree指向一个树
 * 操作后 : 返回树中项目的个数
 ***************************************************************************************/
int TreeItemCount(const Tree *ptree)
{
	return ptree->size;
}

/***************************************************************************************
 * 操作   : 向树中添加一个项目
 * 操作前 : pi指向待添加项目，ptree指向一个已经初始化的树
 * 操作后 : 成功返回true, 否则返回false
 ***************************************************************************************/
bool AddItem(const Item *pi, Tree *ptree)
{
	Node *new_node;

	if (TreeIsFull(ptree)) {
		fprintf(stderr, "tree is full\n");
		return false;
	}
	if (SeekItem(pi, ptree).child != NULL) {
		fprintf(stderr, "Attempted to add duplicate item\n");
		return false;
	}

	new_node = MakeNode(pi);
	if (new_node == NULL) {
		fprintf(stderr, "Couldn't create node\n");
		return false;
	}

	ptree->size++;
	if (ptree->root == NULL) {
		ptree->root = new_node;
	} else {
		AddNode(new_node, ptree->root);
	}

	return true;
}

/***************************************************************************************
 * 操作   : 在树中查找一个项目
 * 操作前 : pi指向待查找的项目，ptree指向一个已经初始化的树
 * 操作后 : 找到返回true, 否则返回false
 ***************************************************************************************/
bool InTree(const Item *pi, const Tree *ptree)
{
	return (SeekItem(pi, ptree).child == NULL) ? false : true;
}

/***************************************************************************************
 * 操作   : 从树中删除一个项目
 * 操作前 : pi指向待删除项目，ptree指向一个已经初始化的树
 * 操作后 : 成功返回true, 否则返回false
 ***************************************************************************************/
bool DeleteItem(const Item *pi, Tree *ptree)
{
	Pair look;

	look = SeekItem(pi, ptree);
	if (look.child == NULL) {
		return false;
	}

	if (look.parent == NULL) {
		DeleteNode(&ptree->root);
	} else if (look.parent->left == look.child) {
		DeleteNode(&look.parent->left);
	} else {
		DeleteNode(&look.parent->right);
	}
	ptree->size--;

	return true;
}

/***************************************************************************************
 * 操作   : 把一个函数作用于树中每一个项目
 * 操作前 : ptree指向一个树, pfun指向一个无返回值的函数,该函数参数为Item
 * 操作后 : pfun指向的函数被作用于树中每个项目一次
 ***************************************************************************************/
void Traverse(const Tree *ptree, void (*pfun)(Item item))
{
	if (ptree != NULL) {
		InOrder(ptree->root, pfun); //使用中序遍历
	}
}

/***************************************************************************************
 * 操作   : 从树中删除所有节点
 * 操作前 : ptree指向一个已经初始化的树
 * 操作后 : 该树为空树
 ***************************************************************************************/
void DeleteAll(Tree *ptree)
{
	if (ptree != NULL) {
		DeleteAllNodes(ptree->root);
	}
	ptree->root = NULL;
	ptree->size = 0;
}

